1. Field of the Invention
The present invention relates to a data processing apparatus for and a data processing method of performing lossless compression encoding of data.
2. Description of the Related Art
Run length encoding (RLE) is one of data compression algorithms and classified as lossless compression. In the run length encoding, consecutive data are encoded by expressing a datum and a number of times the datum continues to compress the continuous data.
For example, a data string “AAAAABBBBBBBBBAAA” is expressible as a data string “A5B9A3” after encoding. This means that “A” continues 5 times, “B” continues 9 times, and then “A” continues 3 times. In this example, a number of times that a datum continues is disposed behind the datum. Alternatively, the number of times that the datum continues may be disposed first and the number of that data may be disposed after the number. In the latter case, the data string of the encoded data is expressed as “5A9B3A.”
In the above-described example, if it is determined beforehand that there are only two types of data, “A” and “B,” and that the datum “A” comes first, the above data string is expressible as only “593.” When following this rule, if the datum “B” is found first, it may be considered that the datum “A” continues zero time first. For example, a data string “BBBAAAABBBBBAAA” is expressible as “03553” after encoding.
As a method of efficiently compressing data, a method of compressing by universal coding has been put into practical use. Universal coding is a lossless data compression method and is applicable to various types of data (for example, character code and object code) since a statistical nature of an information source is not presupposed beforehand upon data compression.
A representative universal coding method is Ziv-Lempel coding. As Ziv-Lempel coding, two algorithms of a universal type and an incremental parsing type have been proposed. One practical method using the universal type algorithm is Lempel-Ziv-Storer-Syzmanski (LZSS) coding. Another practical method using the incremental parsing type algorithm is Lempel-Ziv-Welch (LZW) coding.
In an encoding algorithm of LZ77 coding, which becomes the basis of LZSS coding, encoding data are divided into strings of a maximum length matching from an arbitrary position of a past data string and these are encoded as a duplicate of the past data string.
More specifically, a moving window that stores encoded input data and a lookahead buffer that stores data to be encoded are provided, and a data string of the lookahead buffer is compared with all partial strings of a data string of the moving window to obtain a matching partial string of a maximum length in the moving window. In order to designate this partial string of the maximum length in the moving window, a set of “a start position of the partial string of the maximum length,” “a matching length,” and “a next symbol that yields a mismatch” is encoded.
Next, the encoded data string in the lookahead buffer is moved to the moving window, and a new data string, which corresponds to the encoded data string, is input to the lookahead buffer. Thereafter, the same processing is repeated, so that data is decomposed into partial data strings and encoded.
Generally, in LZSS coding, since it is necessary to detect a longest match with an input data string as many times as the number of the moving windows that store the encoded input data, it is said that an amount of computation is increased but a high compression ratio is achieved.
Further, in an encoding algorithm of LZW coding, a rewritable dictionary is installed, input character strings are sorted into different character strings, and the character strings are designated with numbers in the order they appear and registered into the dictionary. Further, a currently input character string is represented by only a dictionary number of a longest matching character string registered in the dictionary. Compared to LZSS coding, this LZW coding is lower in its compression ratio, but is simpler, easier in its computation, and higher speed processing is possible. Thus, it is widely used in file compression in a storage apparatus or in data transmission.
In the above LZ77 coding, it takes the longest time in searching for the longest matching character string at the time of encoding. Thus, in order to speed up LZ77 coding, it is necessary to speed up the search for the longest matching character string.
Japanese Patent No. 2713369 discloses a two-byte hash method, by a combination of a hash method and a linked list, of obtaining a matching position of two characters, comparing one character by one character for a match of three characters or more, and finally detecting a longest matching position.
Further, as a technique of speeding up hardware processing, Japanese Patent No. 3610381 discloses a structure including an input first in first out (FIFO) 600, a slide FIFO 601, and a search circuit 602 that has as many comparators as the size of the slide as illustrated in FIG. 15. In this structure, the search circuit 602 compares plural data stored in the input FIFO 600 with plural past input data stored in the slide FIFO 601 in parallel and sequentially detects both a longest matching position and a matching length at the same time.
Further, Japanese Patent No. 3730385 discloses a data compression apparatus having a comparator in a place where correlation is likely to occur (for example, directly above or left) in a limited manner, such that a hardware load when having as many comparators as the number of moving windows in parallel is reduced, and processing speed and hardware scale are taken into consideration.
Moreover, Japanese Patent No. 4000266 proposes a method of performing a run length encoding on an index value matching the dictionary by performing Move to Front (MTF) control on a small dynamic dictionary.
Furthermore, Japanese Patent No. 3922386 discloses a technique of obtaining a matching length by comparing plural data at once using a parallel comparing unit.
However, in the above method of Japanese Patent No. 2713369 using the combination of the hash method and the linked list, a two-character 16-bit hash requires a hash table of about 64,000 words. This is effective for software but requires a large capacity for hardware. Consequently, when Japanese Patent No. 2713369 is implemented with small-scale hardware, for example a third character and characters thereafter are compared one character by one character, and thus processing takes time.
Further, in Japanese Patent No. 4000266 performing MTF control using a small dictionary, if the number of words registered in the dictionary is small, for example, if one word is one byte and a depth of the dictionary is 64 words, even if there is a match, 8 bits are just converted to 6 bits. Accordingly, it is necessary to increase the number of words registered in the dictionary, but in that case, it becomes difficult for a match with the dictionary to occur.
In Japanese Patent No. 4000266, in order to solve this, period detection is performed and the number of words of the dictionary is obtained through the period detection as illustrated in FIG. 5. To perform this period detection, a two-pass method or a pipeline-processing on period detection and on an encoding process using a work memory need to be used.
In the two-pass method, processing is divided into two stages: a period detection process and an encoding process. The period detection process is first performed on data to be encoded, and then the encoding process is performed on the data to be encoded using the obtained period. Therefore, the processing takes extra time. Even in the method using the work memory, a large memory area for the pipeline processing of the period detection and the encoding processes is required.
In Japanese Patent No. 3730385, the number of comparators is reducible since the comparators are provided only at places where correlation is likely to occur. However, because plural line memories need to be provided, the hardware scale increases.
Furthermore, in Japanese Patent No. 3610381, the same number of circuits for obtaining a matching length as the number of slides need to be prepared as illustrated in FIG. 9 of the Patent, and the same number of circuits for comparing data as the number of the input FIFOs need to be prepared as illustrated in FIG. 10 of the Patent. Accordingly, a relatively small-scale structure having, for example, a slide length of 32 and 8 input FIFOs is easily implementable, but to increase the compression ratio, a slide length of, for example, 256 or more is required, increasing the scale.
Further, in Japanese Patent No. 3610381, the input FIFO 11 or the slide FIFO must perform shifting of a plurality of data at once based on a matching length. If this process is implemented by hardware, the structure becomes complex. That is, the non-regular shift process or comparison process for the matching length makes the whole hardware complicated. Therefore, in the configuration of Japanese Patent No. 3610381, it is difficult to improve the compression ratio by increasing the number of slides.
Further, in Japanese Patent No. 3610381, in order to obtain the longest matching position and length between the slide and the input data, two kinds of processes, a slide search and a list search, need to be performed. That is, the entire slide is first searched by the slide search, and thereafter the process is switched to the list search of searching from a plurality of matched lists based on the search result of the slide search. When the input data does not match the list, the longest matching length until that time is obtained, and the slide search starts again with that input data.
As described above, in Japanese Patent No. 3610381, when the process is switched to the slide search as no match is obtained in the list search, clock encoding is not performed for a period of at least one clock, and this decreases the processing speed.
Moreover, in Japanese Patent No. 3922386, the processing speed is increased by comparing a plurality of data at once using a matrix array 704 in which a history buffer composed of a latch 700 and a latch 701 and a comparing unit 703, which compares the plurality of data input to an input buffer 702 in a direction perpendicular to the history buffer, are arranged in a matrix of a history buffer length and an input buffer length as illustrated in FIG. 16.
However, in the method of Japanese Patent No. 3922386, the number of data processible at once is limited to the number of data determined by a configuration of the parallel comparing unit. In the example of FIG. 16, the number of data processible in parallel is limited to 12 according to the input byte length of the input buffer 702 of 12 bytes. The number of data processible at once may be increased by increasing the scale of the parallel comparing unit, but this increases the hardware scale and causes restrictions upon installing the hardware in, for example, an ASIC.